\input{euler.tex}

\begin{document}

\problem[333]{Special partitions}

All positive integers can be partitioned in such a way that each and every term of the partition can be expressed as $2^i 3^j$, where $i,j \ge 0$.

Let's consider only those such partitions where none of the terms can divide any of the other terms. For example, the partition of 17 = 2 + 6 + 9 = $2^1 \times 3^0$ + $2^1 \times 3^1 + 2^0 \times 3^2$ would not be valid since 2 can divide 6. Neither would the partition 17 = 16 + 1 = $2^4 \times 3^0 + 2^0 \times 3^0$ since 1 can divide 16. The only valid partition of 17 would be 8 + 9 = $2^3 \times 3^0 + 2^0 \times 3^2$.

Many integers have more than one valid partition, the first being 11 having the following two partitions.
\begin{align}
11 &= 2 + 9 = (2^1 \times 3^0 + 2^0 \times 3^2) . \notag \\
11 &= 8 + 3 = (2^3 \times 3^0 + 2^0 \times 3^1) . \notag
\end{align}

Let $P(n)$ be the number of valid partitions of $n$. For example, $P(11) = 2$.

Let's consider only prime integers $q$ which would have a single valid partition such as $P(17)$. The sum of primes $q \le 100$ such that $P(q)=1$ equals 233.

Find the sum of primes $q \le 10^6$ such that $P(q)=1$.

\solution

Given a positive integer $n$, denote one of its valid partition as
\[
n = \sum_{k=1}^m 2^{i_k} 3^{j_k} ,
\]
where $0 \le i_1 < i_2 < \cdots < i_m$ and $j_1 > j_2 > \cdots > j_m \ge 0$. That is, the exponents of 2 are increasing and the exponents of 3 are decreasing. This must hold because otherwise the term with smaller (or equal) exponents in both 2 and 3 will divide the term with greater (or equal) exponents.

We note two properties of such partitions. First, note that all terms with $i_k \ge 1$ are even. Therefore, if $n$ is odd, then $i_1 = 0$. If $n$ is even, then $i_1 \ge 1$.

Second, for a given even number $2n$, every partition of $2n$ can be uniquely mapped to a partition of $n$, and vice versa. This is because
\[
2n = \sum_{k=1}^m 2^{i_k} 3^{j_k} = 2 \left( \sum_{k=1}^m 2^{i_k-1} 3^{j_k} \right) .
\]

Now we prove that every $n$ can be written as a valid partition. We prove this as follows. First, $n = 1$ can be written as $1 = 2^0 \times 3^0$. Next, suppose all numbers less than $n$ have at least one valid partition. If $n$ is even, partition $n/2$ as 
\[
\frac{n}{2} = \sum_{k=1}^m 2^{i_k} 3^{j_k} .
\]
It is obvious that the following is a valid partition for $n$:
\[
n = \sum_{k=1}^m 2^{i_k+1} 3^{j_k} .
\]
If $n$ is odd, let $j_1 = \lfloor \log_3{n} \rfloor$, i.e. $3^{j_1} \le n < 3^{j_1+1}$. Suppose $n' = n - 3^{j_1}$ (which is even) has the following valid partition
\[
n' = 2^{i_2} 3^{j_2} + \cdots + 2^{i_m} 3^{j_m} ,
\]
where $1 \le i_2 < \cdots < i_m$ and $j_2 > \cdots > j_m$. We need to prove that the following partition of $n$ is also valid
\[
n = 3^{j_1} + n' = 3^{j_1} + 2^{i_2} 3^{j_2} + \cdots + 2^{i_m} 3^{j_m} .
\]
We only need to prove that $j_1 > j_2$. Suppose this is not true, i.e. $j_1 \le j_2$. Then,
\[
n \ge 3^{j_1} + 2 \times 3^{j_2} \ge 3^{j_1} + 2 \times 3^{j_1} = 3^{j_1+1} ,
\]
which is contrary to the pre-condition that $n < 3^{j_1+1}$.

Denote $P(n)$ as the number of valid partitions of $n$. We can find $P(n)$ by trying all possible choices of $3^{j_1}$. Denote $P(n; J) \equiv P(n; j_1 \le J)$ as the number of valid partitions of $n$ such that the 3's exponent in the first term is less than or equal to $J$. Then
\[
P(n) \equiv P(n; j_1 \le \lfloor \log_3{n} \rfloor) .
\]
If $n$ is even, then we have
\[
P(n; J) = P\left(\frac{n}{2}; J\right) .
\]
If $n$ is odd, we have the following recurrence relation
\[
P(n; J) = P(n; J-1) + P( n-3^J ; J - 1) .
\]
The boundary conditions are $P(0; J) = 1$ for all $J$, $P(n; 0) = 0$ for $n > 1$, and $P(1; 0) = 1$.

Once we have computed all $P(n)$ for $1 \le n \le 10^6$, we count the number of primes $q$ such that $P(q) = 1$ to get the answer.

\complexity

Time complexity:

Space complexity:

\answer 

3053105

\end{document} 